package butines.game.steering;

import butines.core.math2d.Vector2D;
import butines.core.math2d.Vector2DUtils;


public class LocalityQueryDB {

	public class ClientProxy {
		private Integer head;
		private ClientProxy prev = null;
		private ClientProxy next = null;
		private Vector2D position = new Vector2D();
		private Object object;
				
		private ClientProxy(Object object) {
			this.object = object;
		}
		
	}
	
	public interface Query {
		
		void found(Object element, float distanceSq, Object queryState);
		
	}
	
	private float originx, originy;
	private float sizex, sizey;
	private int divx, divy;
	private ClientProxy[] bins;
	private int count;
	
	public LocalityQueryDB(float originx, float originy, float sizex, float sizey, int divx, int divy) {
		this.originx = originx;
		this.originy = originy;
		this.sizex = sizex;
		this.sizey = sizey;
		this.divx = divx;
		this.divy = divy;
		
		bins = new ClientProxy[divx * divy + 1];
	}
		
	public int length() {
		return bins.length;
	}
	
	public int count() {
		return count;
	}
	
	public int findIndex(float x, float y) {
		/* if point outside super-brick, return the "other" bin */
		if (x < originx || y < originy || x >= originx + sizex || y >= originy + sizey) {
			return bins.length - 1;
		}
		/* if point inside super-brick, compute the bin coordinates */
		int ix = (int)(((x - originx) / sizex) * divx);
		int iy = (int)(((y - originy) / sizey) * divy);

		/* convert to linear bin number */
		int bin = iy * divx + ix;

		/* return pointer to that bin */
		return bin;
	}
	
	public ClientProxy getBin(int index) {
		return bins[index];
	}
	
	public ClientProxy getOther() {
		return bins[bins.length - 1];
	}
	
	public ClientProxy createBin(Object object) {
		return new ClientProxy(object);
	}
	
	public void add(ClientProxy obj, int index) {
		obj.head = index;
		if (bins[index] == null) {
			obj.prev = null;
			obj.next = null;
		} else {
			obj.prev = null;
			obj.next = bins[index];
			bins[index].prev = obj;
		}
		bins[index] = obj;
		count++;
	}
	
	public void remove(ClientProxy bin) {
		if (bin.head != null) {
			if (bins[bin.head] == bin) {
				bins[bin.head] = bin.next;
			}
			if (bin.prev != null) {
				bin.prev.next = bin.next;
			}
			if (bin.next != null) {
				bin.next.prev = bin.prev;
			}
			count--;
		}
		bin.prev = null;
		bin.next = null;
		bin.head = null;
	}
		
	public void update(ClientProxy bin, Vector2D position) {
		Integer newHead = findIndex(position.x, position.y);
		bin.position.set(position);
		if (bin.head != newHead) {
			remove(bin);
			add(bin, newHead);
		}
	}
	
	public void executeQuery(ClientProxy bin, float radiusSq, Query query, Object queryState, Vector2D center) {
		while (bin != null) {
			float distanceSq = Vector2DUtils.distanceSq(center, bin.position);

			// apply function if client obj within sphere
			if (distanceSq < radiusSq) {
				query.found(bin.object, distanceSq, queryState);
			}

			// consider next client obj in bin list
			bin = bin.next;
		}
	}
	
	public void findObjects(Vector2D center, float radius, Query query, Object queryState) {
		Search search = new Search(center, radius);
		search.findObjects(query, queryState);
	}
	
	public void findObjects(Query query, Object queryState) {
		for (int i = 0; i < bins.length; i++) {
			for (ClientProxy cur = bins[i]; cur != null; cur = cur.next) {
				query.found(cur.object, 0, queryState);
			}
		}
	}
	
	public void removeAllObjects() {
		for (int i = 0; i < bins.length; i++) {
			ClientProxy bin = bins[i];
			while (bin != null) {
				ClientProxy next = bin.next;
				bin.prev = null;
				bin.next = null;
				bin.head = null;
				count--;
				bin = next;
			}
		}
	}

	private class Search {
		Vector2D center;
		float radiusSq;
				
		int minBinX;
		int minBinY;
		int maxBinX;
		int maxBinY;
		
		boolean completeOutside;
		boolean partlyOutside;
		
		Search(Vector2D center, float radius) {
			this.center = center;
			this.radiusSq = radius * radius;
			
			/* is the sphere completely outside the "super brick"? */
			completeOutside = (center.x + radius) < originx
				|| (center.y + radius) < originy
				|| (center.x - radius) >= originx + sizex
				|| (center.y - radius) >= originy + sizey;
				
			/* compute min and max bin coordinates for each dimension */
			minBinX = (int)((((center.x - radius) - originx) / sizex) * divx);
			minBinY = (int)((((center.y - radius) - originy) / sizey) * divy);
			maxBinX = (int)((((center.x + radius) - originx) / sizex) * divx);
			maxBinY = (int)((((center.y + radius) - originy) / sizey) * divy);
			
			/* clip bin coordinates */
			if (minBinX < 0) {
				partlyOutside = true;
				minBinX = 0;
			}
			if (minBinY < 0) {
				partlyOutside = true;
				minBinY = 0;
			}
			if (maxBinX >= divx) {
				partlyOutside = true;
				maxBinX = divx - 1;
			}
			if (maxBinY >= divy) {
				partlyOutside = true; 
				maxBinY = divy - 1; 
			}
				
		}
		
		boolean isCompleteOutside() {
			return completeOutside;
		}
		
		boolean isPartlyOutside() {
			return partlyOutside;
		}
		
		void findObjectsInside(Query query, Object queryState) {
			for (int x = minBinX; x <= maxBinX; x++) {
				for (int y = minBinY; y <= maxBinY; y++) {
					ClientProxy bin = bins[y * divx + x];
					executeQuery(bin, radiusSq, query, queryState, center);
				}
			}
		}
		
		void findObjectsOutsite(Query query, Object queryState) {
			executeQuery(getOther(), radiusSq, query, queryState, center);
		}
		
		void findObjects(Query query, Object queryState) {
			if (isCompleteOutside()) {
				findObjectsOutsite(query, queryState);
				return;
			}
			if (isPartlyOutside()) {
				findObjectsOutsite(query, queryState);
			}		
			findObjectsInside(query, queryState);
		}
		
	}
	
}
